package q34_searchRange;

public class Solution_2 {
    public int[] searchRange(int[] nums, int target) {
        if (nums.length == 0) return new int[] {-1, -1};
        int low = BinarySearchLow(nums, target);
        int high = BinarySearchHigh(nums, target) - 1;// 需要减1
        if (low == nums.length || nums[low] != target) return new int[] {-1, -1};
        return new int[] {low, high};
    }

    private int BinarySearchHigh(int[] nums, int target) {
        int low = 0, high = nums.length - 1;
        while (low < high) {
            int mid = low + ((high - low) >> 1);
            if (nums[mid] > target) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }

    private int BinarySearchLow(int[] nums, int target) {
        int low = 0, high = nums.length - 1;
        while (low < high) {
            int mid = low + ((high - low) >> 1);
            if (nums[mid] >= target) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }
}
